package LC;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.com/problems/contains-duplicate-ii/description/
 * Given an array of integers and an integer k,
 * find out whether there are two distinct indices i and j
 * in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.
 */
public class LC_219_ContainsDuplicateII_HashMap {
    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3, 4, 5, 3, 1, 3};
        int k = 3;
        boolean res = Solution.containsNearbyDuplicate(nums, k);
        System.out.println(res);
    }

    static class Solution {
        static boolean containsNearbyDuplicate(int[] nums, int k) {
            if (nums == null || nums.length < 2 || k < 1) return false;
            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < nums.length; i++) {
                if (!map.containsKey(nums[i])) {
                    map.put(nums[i], i);
                } else {
                    int value = map.get(nums[i]);
                    if (i - value <= k) return true;
                    map.put(nums[i], i);
                }
            }
            return false;
        }
    }
}